We will consider P-graph complexes, where P is a cyclic operad. P-graph complexes are natural generalizations of Kontsevich's graph complexes -- for P = the operad for associative algebras it is the complex of ribbon graphs, for P = the operad for commutative associative algebras, the complex of all graphs. We construct a `universal class' in the cohomology of the graph complex with coefficients in a theory. The Kontsevich-type invariant is then an evaluation, on a concrete cyclic algebra, of this class. We also explain some results of M. Penkava and A. Schwarz on the construction of an invariant from a cyclic deformation of a cyclic algebra. Our constructions are illustrated by a `toy model' of tree complexes.